Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:

Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Solution:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  10.   public ListNode reverseBetween(ListNode head, int m, int n) {
  11.     if (head == null || head.next == null) {
  12.         return head;
  13.     }
  15.     int k = n - m + 1;
  17.     ListNode f = new ListNode(0);
  18.     f.next = head;
  20.     ListNode p = f;
  21.     ListNode c = head;
  23.     // locate the m-th node
  24.     while (m > 1) {
  25.       p = c;
  26.       c = c.next;
  27.       m--;
  28.     }
  30.     // reverse till n-th node
  31.     ListNode prev = null;
  32.     ListNode curr = c;
  33.     ListNode next = null;
  35.     while (k > 0) {
  36.       next = curr.next;
  37.       curr.next = prev;
  38.       prev = curr;
  39.       curr = next;
  40.       k--;
  41.     }
  43.     // re-link
  44.     p.next = prev;
  45.     c.next = curr;
  47.     return f.next;
  48.   }
  49. }